"""
3393. 统计异或值为给定值的路径数目
中等
相关标签
相关企业
提示
给你一个大小为 m x n 的二维整数数组 grid 和一个整数 k 。

你的任务是统计满足以下 条件 且从左上格子 (0, 0) 出发到达右下格子 (m - 1, n - 1) 的路径数目：

每一步你可以向右或者向下走，也就是如果格子存在的话，可以从格子 (i, j) 走到格子 (i, j + 1) 或者格子 (i + 1, j) 。
路径上经过的所有数字 XOR 异或值必须 等于 k 。
请你返回满足上述条件的路径总数。

由于答案可能很大，请你将答案对 109 + 7 取余 后返回。



示例 1：

输入：grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]], k = 11

输出：3

解释：

3 条路径分别为：

(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2)
(0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2)
(0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)
示例 2：

输入：grid = [[1, 3, 3, 3], [0, 3, 3, 2], [3, 0, 1, 1]], k = 2

输出：5

解释：

5 条路径分别为：

(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (2, 3)
(0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2) → (2, 3)
(0, 0) → (1, 0) → (1, 1) → (1, 2) → (1, 3) → (2, 3)
(0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2) → (2, 3)
(0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) → (2, 3)
示例 3：

输入：grid = [[1, 1, 1, 2], [3, 0, 3, 2], [3, 0, 2, 2]], k = 10

输出：0



提示：

1 <= m == grid.length <= 300
1 <= n == grid[r].length <= 300
0 <= grid[r][c] < 16
0 <= k < 16
"""


class Solution(object):
    def countPathsWithXorValue(self, grid, k):
        """
        :type grid: List[List[int]]
        :type k: int
        :rtype: int
        """
        #思路，把每个可能的值存在二维数组值为的map中，key为出现的数字，value为次数
        mod = 10 ** 9 + 7
        m = len(grid)
        n = len(grid[0])
        #定义个二维数字，值是dict
        dp = [[dict() for _ in range(len(grid[0]))] for _ in range(len(grid))]
        #用for写法,定义个二维数字，值是dict
        # dp = []
        # for i in range(m):
        #     row = []
        #     for j in range(n):
        #         row.append(dict())
        #     dp.append(row)
        #初始化,0,0位置的值为grid[0][0]出现次数为1
        dp[0][0][grid[0][0]] = 1
        for i in range(1,m):
            dp[i][0] = merge(dp[i-1][0], grid[i][0])
        for j in range(1,n):
            dp[0][j] = merge(dp[0][j-1], grid[0][j])
        for i in range(1,m):
            for j in range(1,n):
                #遍历dp[i-1][j]和dp[i][j-1]的key和value，key要和grid[i][j]异或得到新的map
                map1 = merge(dp[i-1][j], grid[i][j])
                map2 = merge(dp[i][j-1], grid[i][j])
                #合并两个map
                dp[i][j] = mergeMap(map1, map2)
        #判断k是否存在
        if k in dp[m-1][n-1]:
            return dp[m-1][n-1][k]%mod
        return 0

def mergeMap(map1, map2):
    """
    :param map1: map
    :param map2: map
    :return:
    """
    #合并两个map
    mod = 10 ** 9 + 7
    map3 = dict()
    for key, value in map1.items():
        map3[key] = value
    for key, value in map2.items():
        if key in map3:
            map3[key] = (map3[key] + value)%mod
        else:
            map3[key] = value
    return map3
def merge(map1, num1):
    """
    :param map1: map
    :param num1: int
    :return:
    """
    #遍历map的key和value，key要和num异或得到新的map
    map2 = dict()
    for key, value in map1.items():
        newKey = key ^ num1
        map2[newKey] = value
    return map2



if __name__ == '__main__':
    # #输入二进制
    # i1 = 0b101
    # i2 = 0b01
    # #亦或
    # print(i1 ^ i2)
    # dp = [[0] * 10 for i in range(0,9)]
    # # print(dp)
    # dp = [[0 for j in range(0,10)] for i in range(0,9)]
    # print(dp)
    grid = [[2,1,5], [7,10,0], [12,6,4]]
    k = 11
    # print(Solution().countPathsWithXorValue(grid, k))
    grid = [[1,1,1,2],[3,0,3,2],[3,0,2,2]]
    k = 10
    print(Solution().countPathsWithXorValue(grid, k))
